// 归并排序
const arr = [5, 3, 4, 1, 2, 8, 7, 6, 9, 0];

const merge_sort = (arr, l, r) => {
  if (l >= r) return;
  let mid = (l + r) >> 1;
  merge_sort(arr, l, mid);
  merge_sort(arr, mid + 1, r);

  let p1 = l, // 左指针
    p2 = mid + 1, // 右指针
    k = 0, // 标记临时数组的最后位置
    tem = []; // 临时数组

  // 合并
  while (p1 <= mid || p2 <= r) {
    if ((p2 > r) || (p1 <= mid && arr[p1] <= arr[p2])) { // 右侧已结束 或 左侧小于右侧
      tem[k] = arr[p1++];  // 放入临时数组，k指针后移一位
    } else {
      tem[k] = arr[p2++];
    }
    k++;
  }
  // 拷贝回原数组中
  for (let i = l; i <= r; i++) {
    arr[i] = tem[i - l];
  }
}

merge_sort(arr, 0, arr.length - 1)
console.log(arr);